package com.ywk.base.dataStructure.recursion;

public class MIGong {

	public static void main(String[] args) {
		System.out.println(Math.pow(8, 8));
		int[][] map=new int[8][7];
		//设置上下挡板
		for(int i=0;i<7;i++) {
			map[0][i]=1;
			map[7][i]=1;
		}
		//设置左右挡板
		for (int i = 1; i < 7; i++) {
			map[i][0]=1;
			map[i][6]=1;
		}
		//设置挡板
		map[3][1]=1;
		map[3][2]=1;
		map[2][2]=1;
		System.out.println("原地图:");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]+"  ");
			}
			System.out.println();
		}
		setWay(map, 1, 1);
		System.out.println("找到路：");
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]+"  ");
			}
			System.out.println();
		}
	}
	
	//策略：下->右->上->左
	public static boolean setWay(int map[][],int i,int j) {
		if(map[2][3]==2) {
			return true;//找到目标位置后将true返回到调用它的地方
		}else {
			if(map[i][j]==0) {
				map[i][j]=2;
				//一直递归向下走，直到遇到条件不满足执行到标记1时，返回false，不进入当前if语句方法体，
				//去执行判断下面的else if语句条件
				if(setWay(map, i+1, j)) {//向下
					return true;
				}else if(setWay(map, i, j+1)) {//向右
					return true;
				}else if(setWay(map, i-1, j)) {//向上
					return true;
				}else if(setWay(map, i, j-1)) {//向左
					return true;
				}else {
					map[i][j]=3;//回溯：该点的任意方向都走不通时返回上一级(即调用此函数的地方)
					return false;
				}
			}else {
				return false;//标记1
			}
			
		}
	}

}
